package leetcode.editor.cn;

public class _105_ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public static void main(String[] args) {
        Solution solution = new _105_ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
        int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        solution.buildTree(preorder, inorder);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
            if (preStart > preEnd) {
                return null;
            }
            int idx = inStart;
            while (inorder[idx] != preorder[preStart]) {
                idx++;
            }
            TreeNode left = buildTree(preorder, preStart + 1, preStart + idx - inStart, inorder, inStart, idx - 1);
            TreeNode right = buildTree(preorder, preStart + idx - inStart + 1, preEnd, inorder, idx + 1, inEnd);
            return new TreeNode(preorder[preStart], left, right);

        }

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}